{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #The Number of Beautiful Subsets"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #dynamic-programming #backtracking"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #动态规划 #回溯"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: beautifulSubsets"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #美丽子集的数目"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个由正整数组成的数组 <code>nums</code> 和一个 <strong>正</strong> 整数 <code>k</code> 。</p>\n",
    "\n",
    "<p>如果 <code>nums</code> 的子集中，任意两个整数的绝对差均不等于 <code>k</code> ，则认为该子数组是一个 <strong>美丽</strong> 子集。</p>\n",
    "\n",
    "<p>返回数组 <code>nums</code> 中 <strong>非空</strong> 且 <strong>美丽</strong> 的子集数目。</p>\n",
    "\n",
    "<p><code>nums</code> 的子集定义为：可以经由 <code>nums</code> 删除某些元素（也可能不删除）得到的一个数组。只有在删除元素时选择的索引不同的情况下，两个子集才会被视作是不同的子集。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>nums = [2,4,6], k = 2\n",
    "<strong>输出：</strong>4\n",
    "<strong>解释：</strong>数组 nums 中的美丽子集有：[2], [4], [6], [2, 6] 。\n",
    "可以证明数组 [2,4,6] 中只存在 4 个美丽子集。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>nums = [1], k = 1\n",
    "<strong>输出：</strong>1\n",
    "<strong>解释：</strong>数组 nums 中的美丽数组有：[1] 。\n",
    "可以证明数组 [1] 中只存在 1 个美丽子集。 \n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= nums.length &lt;= 20</code></li>\n",
    "\t<li><code>1 &lt;= nums[i], k &lt;= 1000</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [the-number-of-beautiful-subsets](https://leetcode.cn/problems/the-number-of-beautiful-subsets/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [the-number-of-beautiful-subsets](https://leetcode.cn/problems/the-number-of-beautiful-subsets/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[2,4,6]\\n2', '[1]\\n1']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def beautifulSubsets(self, nums: List[int], k: int) -> int:\n",
    "        groups = defaultdict(Counter)\n",
    "        for x in nums:\n",
    "            groups[x % k][x] += 1\n",
    "        ans = 1\n",
    "        for cnt in groups.values():\n",
    "            g = sorted(cnt.items())\n",
    "            m = len(g)\n",
    "            f = [0]*(m+1)\n",
    "            f[0] = 1\n",
    "            f[1] = 1 << g[0][1]\n",
    "            for i in range(1,m):\n",
    "                if g[i][0] - g[i-1][0] == k:\n",
    "                    f[i+1] = f[i] + f[i-1] * ((1<<g[i][1]) - 1)\n",
    "                else:\n",
    "                    f[i+1] = f[i] << g[i][1]\n",
    "            ans *= f[m]\n",
    "        return ans - 1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def beautifulSubsets(self, nums: List[int], k: int) -> int:\n",
    "        cnt = defaultdict(Counter)\n",
    "        for num in nums:\n",
    "            cnt[num%k][num] += 1\n",
    "        ans = 1\n",
    "        for count in cnt.values():\n",
    "            g = sorted(count.items())\n",
    "            m = len(g)\n",
    "            f = [0] * (m + 1)\n",
    "            f[0] = 1\n",
    "            f[1] = 1<<g[0][1]\n",
    "            for i in range(1, m):\n",
    "                if g[i][0] - g[i-1][0] == k:\n",
    "                    f[i+1] = f[i] + f[i-1] * ((1<<g[i][1]) - 1)\n",
    "                else:\n",
    "                    f[i+1] = f[i] * (1<<g[i][1])\n",
    "            ans *= f[m]\n",
    "        return ans -1 \n",
    "\n",
    "\n",
    "        groups = defaultdict(Counter)\n",
    "        for x in nums:\n",
    "            groups[x % k][x] += 1\n",
    "        ans = 1\n",
    "        for cnt in groups.values():\n",
    "            g = sorted(cnt.items())\n",
    "            m = len(g)\n",
    "            f = [0] * (m + 1)\n",
    "            f[0] = 1\n",
    "            f[1] = 1 << g[0][1]\n",
    "            for i in range(1, m):\n",
    "                if g[i][0] - g[i - 1][0] == k:\n",
    "                    f[i + 1] = f[i] + f[i - 1] * ((1 << g[i][1]) - 1)\n",
    "                else:\n",
    "                    f[i + 1] = f[i] << g[i][1]\n",
    "            ans *= f[m]\n",
    "        return ans - 1  # -1 去掉空集\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "powers = [1]\n",
    "for _ in range(20):\n",
    "    powers.append(powers[-1] * 2)\n",
    "\n",
    "def count(vals):\n",
    "    acc = 1\n",
    "    last = 0\n",
    "    for count in vals:\n",
    "        last = (acc - last) * (powers[count] - 1)\n",
    "        acc += last\n",
    "    return acc\n",
    "\n",
    "class Solution:\n",
    "    def beautifulSubsets(self, nums: List[int], k: int) -> int:\n",
    "        cnt = Counter(nums)\n",
    "        ans = 1\n",
    "        for item in cnt:\n",
    "            if item - k not in cnt:\n",
    "                vals = []\n",
    "                while item in cnt:\n",
    "                    vals.append(cnt[item])\n",
    "                    item += k\n",
    "                ans *= count(vals)\n",
    "        return ans - 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def beautifulSubsets(self, nums: List[int], k: int) -> int:\n",
    "        ret = [0]\n",
    "        self.func([],nums,k,ret)\n",
    "        return ret[0]\n",
    "    def func(self,chosen,choice,k,out):\n",
    "        for i,choose in enumerate(choice):\n",
    "            if (choose-k in chosen) or (choose+k in chosen):\n",
    "                pass\n",
    "            else:\n",
    "                chosen.append(choose)\n",
    "                out[0]+=1\n",
    "                self.func(chosen,choice[i+1:],k,out)\n",
    "                chosen.pop()\n",
    "        return"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def beautifulSubsets(self, nums: List[int], k: int) -> int:\n",
    "        groups = defaultdict(Counter)\n",
    "        for x in nums:\n",
    "            groups[x % k][x] += 1\n",
    "        ans = 1\n",
    "        for cnt in groups.values():\n",
    "            g = sorted(cnt.items())\n",
    "            m = len(g)\n",
    "            f = [0] * (m + 1)\n",
    "            f[0] = 1\n",
    "            f[1] = 1 << g[0][1]\n",
    "            for i in range(1, m):\n",
    "                if g[i][0] - g[i - 1][0] == k:\n",
    "                    f[i + 1] = f[i] + f[i - 1] * ((1 << g[i][1]) - 1)\n",
    "                else:\n",
    "                    f[i + 1] = f[i] << g[i][1]\n",
    "            ans *= f[m]\n",
    "        return ans - 1  # -1 去掉空集"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def beautifulSubsets(self, nums: List[int], k: int) -> int:\n",
    "        g = defaultdict(Counter)\n",
    "\n",
    "        for x in nums:\n",
    "            g[x%k][x]+=1\n",
    "        ans =1 \n",
    "        for cnt in g.values():\n",
    "            group = sorted(cnt.items())\n",
    "            m =len(group)\n",
    "            f = [0]*(m+1)\n",
    "            f[0]=1\n",
    "            f[1] =1<<group[0][1]\n",
    "            for i in range(1,m):\n",
    "                if group[i][0]-group[i-1][0]==k:\n",
    "                    f[i+1]=f[i]+f[i-1]*((1<<group[i][1])-1)\n",
    "                else:\n",
    "                    f[i+1]=f[i]<<group[i][1]\n",
    "            ans *= f[m] \n",
    "        return ans -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import time\n",
    "\n",
    "powers = [1]\n",
    "for _ in range(20):\n",
    "    powers.append(powers[-1] * 2)\n",
    "\n",
    "def count(vals):\n",
    "    acc = 1\n",
    "    last = 0\n",
    "    for count in vals:\n",
    "        last = (acc - last) * (powers[count] - 1)\n",
    "        acc += last\n",
    "    return acc\n",
    "\n",
    "class Solution:\n",
    "    def beautifulSubsets(self, nums: List[int], k: int) -> int:\n",
    "        cnt = Counter(nums)\n",
    "        ans = 1\n",
    "        for item in cnt:\n",
    "            if item - k not in cnt:\n",
    "                vals = []\n",
    "                while item in cnt:\n",
    "                    vals.append(cnt[item])\n",
    "                    item += k\n",
    "                ans *= count(vals)\n",
    "        time.sleep(0.008)\n",
    "        return ans - 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def beautifulSubsets(self, nums: List[int], k: int) -> int:\n",
    "        n=len(nums)\n",
    "        ans=0\n",
    "        cnt=Counter()\n",
    "        def dfs(i):\n",
    "            nonlocal ans\n",
    "            ans += 1\n",
    "            if i==n:\n",
    "                return\n",
    "            for a in range(i,n):\n",
    "                if cnt[nums[a]-k]==0 and cnt[nums[a]+k]==0:\n",
    "                    cnt[nums[a]] += 1\n",
    "                    dfs(a+1)\n",
    "                    cnt[nums[a]]-= 1\n",
    "        dfs(0)\n",
    "        return ans-1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def beautifulSubsets(self, nums: List[int], k: int) -> int:\n",
    "        groups = defaultdict(Counter)\n",
    "        for x in nums:\n",
    "            groups[x % k][x] += 1\n",
    "        ans = 1\n",
    "        for cnt in groups.values():\n",
    "            g = sorted(cnt.items())\n",
    "            m = len(g)\n",
    "            f = [0] * (m + 1)\n",
    "            f[0] = 1\n",
    "            f[1] = 1 << g[0][1]\n",
    "            for i in range(1, m):\n",
    "                if g[i][0] - g[i - 1][0] == k:\n",
    "                    f[i + 1] = f[i] + f[i - 1] * ((1 << g[i][1]) - 1)\n",
    "                else:\n",
    "                    f[i + 1] = f[i] << g[i][1]\n",
    "            ans *= f[m]\n",
    "        return ans - 1  # -1 去掉空集\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def beautifulSubsets(self, nums: List[int], k: int) -> int:\n",
    "        cnt = Counter(nums)\n",
    "        ans = 1\n",
    "        for num in cnt:\n",
    "            if not cnt[num - k]:\n",
    "                lst = []\n",
    "                while cnt[num]:\n",
    "                    lst.append(cnt[num])\n",
    "                    num += k\n",
    "                m = len(lst)\n",
    "                # if m == 1:\n",
    "                #     ans *= pow(2, lst[0])\n",
    "                #     continue\n",
    "                # if m == 2:\n",
    "                #     ans *= (pow(2, lst[0])+pow(2, lst[1]))\n",
    "\n",
    "                dp = [0] * (m + 1)\n",
    "                dp[0] = 1\n",
    "                for i, c in enumerate(lst):\n",
    "                    dp[i + 1] = dp[i]  # 不选\n",
    "                    # 选\n",
    "                    if i:\n",
    "                        dp[i + 1] += dp[i - 1] * (pow(2, c)-1)\n",
    "                    else:\n",
    "                        dp[i + 1] += pow(2, c) - 1\n",
    "                ans *= dp[-1]\n",
    "        return ans - 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.path = {}\n",
    "        self.result = 0\n",
    "    def beautifulSubsets(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        def backtracking(start):\n",
    "            if(start == n):\n",
    "                return\n",
    "            for i in range(start,n):\n",
    "                if(nums[i]+k not in self.path and nums[i]-k not in self.path):\n",
    "                    if(nums[i] not in self.path):\n",
    "                        self.path[nums[i]] = 0\n",
    "                    self.path[nums[i]] += 1\n",
    "                    self.result += 1\n",
    "                    backtracking(i+1)\n",
    "                    self.path[nums[i]] -= 1\n",
    "                    if(self.path[nums[i]] == 0):\n",
    "                        del self.path[nums[i]]\n",
    "            return \n",
    "        backtracking(0)\n",
    "        return self.result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def beautifulSubsets(self, nums: List[int], k: int) -> int:\n",
    "        groups = defaultdict(lambda: defaultdict(lambda: 0))\n",
    "        for n in nums:\n",
    "            groups[n%k][n] += 1\n",
    "\n",
    "        ans = 1\n",
    "        for g_dict in groups.values():\n",
    "            g = sorted(g_dict.items())\n",
    "            f = defaultdict(lambda: 0)\n",
    "            \n",
    "            for i, (x, cnt) in enumerate(g):\n",
    "                if i == 0:\n",
    "                    f[(0, 0)] = 1\n",
    "                    f[(0, 1)] = 2**cnt - 1\n",
    "                else:\n",
    "                    if x - g[i-1][0] == k:\n",
    "                        f[(i, 0)] = f[(i-1, 1)] + f[(i-1, 0)]\n",
    "                        f[(i, 1)] = f[(i-1, 0)] * (2**cnt-1)\n",
    "                    else:\n",
    "                        f[(i, 0)] = f[(i-1, 1)] + f[(i-1, 0)]\n",
    "                        f[(i, 1)] = (f[(i-1, 0)] + f[(i-1, 1)])* (2**cnt-1) \n",
    "            ans = ans * (f[(i, 0)] + f[(i, 1)])\n",
    "\n",
    "        return ans - 1  # -1 去掉空集"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def beautifulSubsets(self, nums: List[int], k: int) -> int:\n",
    "\n",
    "        def bt(i):\n",
    "            if i == len(nums):\n",
    "                return 1\n",
    "            res = 0\n",
    "            if not path or ((nums[i] - k ) not in path and (nums[i]+k) not in path):\n",
    "                if nums[i] in path:\n",
    "                    path[nums[i]] += 1\n",
    "                else:\n",
    "                    path[nums[i]] = 1\n",
    "                res += bt(i+1)\n",
    "                path[nums[i]] -= 1\n",
    "                if path[nums[i]] == 0:\n",
    "                    path.pop(nums[i])\n",
    "            \n",
    "            res += bt(i+1)\n",
    "            return res\n",
    "\n",
    "        path = {}\n",
    "        return bt(0) - 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.path = []\n",
    "        self.result = 0\n",
    "    def beautifulSubsets(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        def backtracking(start):\n",
    "            if(start == n):\n",
    "                return\n",
    "            for i in range(start,n):\n",
    "                if(nums[i]+k not in self.path and nums[i]-k not in self.path):\n",
    "                    self.path.append(nums[i])\n",
    "                    self.result += 1\n",
    "                    backtracking(i+1)\n",
    "                    self.path.pop()\n",
    "            return \n",
    "        backtracking(0)\n",
    "        return self.result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def beautifulSubsets(self, nums: List[int], k: int) -> int:\n",
    "        # 2**n-1-非美丽子集个数\n",
    "        def dfs(i):\n",
    "            if i==n:\n",
    "                nonlocal ans \n",
    "                ans+=1\n",
    "                return \n",
    "            dfs(i+1)\n",
    "            if pos[nums[i]-k]==0 and pos[nums[i]+k]==0:\n",
    "                pos[nums[i]]+=1\n",
    "                dfs(i+1)\n",
    "                pos[nums[i]]-=1\n",
    "        ans=0\n",
    "        n=len(nums)\n",
    "        pos=Counter()\n",
    "        dfs(0)\n",
    "        return ans-1\n",
    "                \n",
    "                \n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def beautifulSubsets(self, nums: List[int], k: int) -> int:\n",
    "        res, ct = 1, Counter(nums)\n",
    "        for x in ct:\n",
    "            if x-k not in ct:\n",
    "                a, b = 1, 1\n",
    "                while x in ct:\n",
    "                    a, b = b, b+(pow(2,ct[x])-1)*a\n",
    "                    x += k\n",
    "                res *= b\n",
    "        return res-1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def beautifulSubsets(self, nums: List[int], k: int) -> int:\n",
    "        nums=sorted(nums)\n",
    "        result=[]\n",
    "        used=[0]*len(nums)\n",
    "        self.res=0\n",
    "        def dfs(l,tmp):\n",
    "            \n",
    "            if len(tmp)>0:\n",
    "                self.res+=1\n",
    "            for i in range(l,len(nums)):\n",
    "                n=nums[i]\n",
    "                if used[i]: continue\n",
    "                if  n-k   in set(tmp) or  n+k   in set(tmp):\n",
    "                    continue\n",
    "                used[i]=1\n",
    "                tmp.append(n)\n",
    "                dfs(i+1,tmp)\n",
    "                tmp.pop()\n",
    "                used[i]=0\n",
    "        dfs(0,[])\n",
    "        # print(result)\n",
    "        return self.res\n",
    "\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def beautifulSubsets(self, nums: List[int], k: int) -> int:\n",
    "        groups = defaultdict(Counter)\n",
    "        for x in nums:\n",
    "            groups[x % k][x] += 1\n",
    "        ans = 1\n",
    "        for cnt in groups.values():\n",
    "            g = sorted(cnt.items())\n",
    "            m = len(g)\n",
    "            f = [0] * (m + 1)\n",
    "            f[0] = 1\n",
    "            f[1] = 1 << g[0][1]\n",
    "            for i in range(1, m):\n",
    "                if g[i][0] - g[i - 1][0] == k:\n",
    "                    f[i + 1] = f[i] + f[i - 1] * ((1 << g[i][1]) - 1)\n",
    "                else:\n",
    "                    f[i + 1] = f[i] << g[i][1]\n",
    "            ans *= f[m]\n",
    "        return ans - 1  # -1 去掉空集\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def beautifulSubsets(self, nums: List[int], k: int) -> int:\n",
    "        ans = 0\n",
    "        path = collections.defaultdict(int)\n",
    "        def dfs(i: int):\n",
    "            nonlocal ans,  path\n",
    "            if i < 0:\n",
    "                ans += 1\n",
    "                return\n",
    "            \n",
    "            # 选\n",
    "            if path[nums[i] + k] == 0 and path[nums[i] - k] == 0:\n",
    "                path[nums[i]] += 1\n",
    "                dfs(i - 1)\n",
    "                path[nums[i]] -= 1\n",
    "            # 不选\n",
    "            dfs(i - 1)\n",
    "\n",
    "        n = len(nums)\n",
    "        dfs(n-1)\n",
    "        return ans - 1 # 多出一个全不选"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def beautifulSubsets(self, nums: List[int], k: int) -> int:\n",
    "        groups = defaultdict(lambda: defaultdict(lambda: 0))\n",
    "        for n in nums:\n",
    "            groups[n%k][n] += 1\n",
    "\n",
    "        ans = 1\n",
    "        for g_dict in groups.values():\n",
    "            g = sorted(g_dict.items())\n",
    "            f = defaultdict(lambda: 0)\n",
    "            \n",
    "            for i, (x, cnt) in enumerate(g):\n",
    "                if i == 0:\n",
    "                    f[(0, 0)] = 1\n",
    "                    f[(0, 1)] = 2**cnt - 1\n",
    "                else:\n",
    "                    if x - g[i-1][0] == k:\n",
    "                        f[(i, 0)] = f[(i-1, 1)] + f[(i-1, 0)]\n",
    "                        f[(i, 1)] = f[(i-1, 0)] * (2**cnt-1)\n",
    "                    else:\n",
    "                        f[(i, 0)] = f[(i-1, 1)] + f[(i-1, 0)]\n",
    "                        f[(i, 1)] = (f[(i-1, 0)] + f[(i-1, 1)])* (2**cnt-1) \n",
    "            ans = ans * (f[(i, 0)] + f[(i, 1)])\n",
    "\n",
    "        return ans - 1  # -1 去掉空集"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def beautifulSubsets(self, nums: List[int], k: int) -> int:\n",
    "\n",
    "        res = 0\n",
    "        n = len(nums)\n",
    "\n",
    "        def isB(path: List[int], num: int, k: int) -> bool:\n",
    "            for m in path:\n",
    "                if abs(num - m) == k:\n",
    "                    return False\n",
    "            return True\n",
    "\n",
    "\n",
    "        def backtrack(path: List[int], index: int):\n",
    "            nonlocal res\n",
    "            if index >= n:\n",
    "                return\n",
    "            for i in range(index, n):\n",
    "                if isB(path, nums[i], k):\n",
    "                    res += 1\n",
    "                    path.append(nums[i])\n",
    "                    backtrack(path, i+1)\n",
    "                    path.pop()\n",
    "\n",
    "        path = []\n",
    "\n",
    "        backtrack(path, 0)\n",
    "\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def beautifulSubsets(self, nums: List[int], k: int) -> int:\n",
    "        nums.sort()\n",
    "        path = []\n",
    "        ans = 0\n",
    "        mp = defaultdict(int)\n",
    "        def dfs(i: int):\n",
    "            if i < 0:\n",
    "                nonlocal ans\n",
    "                ans += 1\n",
    "                return\n",
    "            dfs(i - 1)\n",
    "            if mp[nums[i] + k] == 0:\n",
    "                path.append(nums[i])\n",
    "                mp[nums[i]] += 1\n",
    "                dfs(i - 1)\n",
    "                mp[nums[i]] -= 1\n",
    "                path.pop()\n",
    "        dfs(len(nums) - 1)\n",
    "        return ans - 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def beautifulSubsets(self, nums: List[int], k: int) -> int:\n",
    "        def dfs(idx):\n",
    "            if idx == len(nums):\n",
    "                self.count += 1\n",
    "                return\n",
    "\n",
    "            # take idx\n",
    "            # we can take num = nums[idx) only if its not illegal (for x in subset num is not x - k and not x + k)\n",
    "            x = nums[idx]\n",
    "            if illegal[x] == 0:\n",
    "                illegal[x-k]+=1\n",
    "                illegal[x + k]+=1\n",
    "                dfs(idx + 1)\n",
    "                illegal[x- k]-=1\n",
    "                illegal[x + k]-=1\n",
    "            # dont take idx\n",
    "            dfs(idx +1)\n",
    "        illegal = collections.defaultdict(int)\n",
    "        self.count =0\n",
    "        dfs(0)\n",
    "        return self.count - 1 # -1 to remove empty subset"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def beautifulSubsets(self, nums: List[int], k: int) -> int:\n",
    "        nums=sorted(nums)\n",
    "        result=[]\n",
    "        used=[0]*len(nums)\n",
    "        self.res=0\n",
    "        def dfs(l,tmp):\n",
    "            \n",
    "            if len(tmp)>0:\n",
    "                self.res+=1\n",
    "            for i in range(l,len(nums)):\n",
    "                n=nums[i]\n",
    "                if used[i]: continue\n",
    "                if  n-k   in tmp or  n+k   in tmp:\n",
    "                    continue\n",
    "                used[i]=1\n",
    "                tmp.append(n)\n",
    "                dfs(i+1,tmp)\n",
    "                tmp.pop()\n",
    "                used[i]=0\n",
    "        dfs(0,[])\n",
    "        # print(result)\n",
    "        return self.res\n",
    "\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def beautifulSubsets(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        result = 0\n",
    "        sub = list()\n",
    "        counter = defaultdict(int)\n",
    "\n",
    "        def dfs(i):\n",
    "            nonlocal result\n",
    "            if i == n:\n",
    "                if sub:\n",
    "                    result += 1\n",
    "                return\n",
    "            dfs(i+1)\n",
    "            if counter[nums[i] - k] == 0 and counter[nums[i] + k] == 0:\n",
    "                sub.append(nums[i])\n",
    "                counter[nums[i]] += 1\n",
    "                dfs(i+1)\n",
    "                sub.pop()\n",
    "                counter[nums[i]] -= 1\n",
    "\n",
    "        dfs(0)\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def beautifulSubsets(self, nums: List[int], k: int) -> int:\n",
    "        ans = 0\n",
    "        m = defaultdict(int)\n",
    "        n = len(nums)\n",
    "\n",
    "        def dfs(i):\n",
    "            if i == n: return 1\n",
    "            ans = dfs(i+1)\n",
    "            num = nums[i]\n",
    "            if m[num-  k] == 0 and m[num + k] == 0:\n",
    "                m[num] += 1\n",
    "                ans += dfs(i+1)\n",
    "                m[num] -= 1\n",
    "            return ans\n",
    "        \n",
    "        return dfs(0) - 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def beautifulSubsets(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        def g(p):\n",
    "            for x in p:\n",
    "                for y in p:\n",
    "                    if abs(x-y) == k:\n",
    "                        return False\n",
    "            return True\n",
    "        \n",
    "        v = defaultdict(lambda:0)\n",
    "        cnt = 0\n",
    "        tmp = []\n",
    "        def f(i):\n",
    "            nonlocal cnt\n",
    "            if i == n:\n",
    "                cnt += 1\n",
    "            else:\n",
    "                if v[nums[i]+k] or v[nums[i]-k]:\n",
    "                    f(i+1)\n",
    "                else:\n",
    "                    tmp.append(nums[i])\n",
    "                    v[nums[i]] += 1\n",
    "                    f(i+1)\n",
    "                    tmp.pop()\n",
    "                    v[nums[i]] -= 1\n",
    "                    f(i+1)\n",
    "        f(0)\n",
    "        return cnt - 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def beautifulSubsets(self, nums: List[int], k: int) -> int:\n",
    "        n=len(nums)\n",
    "        nums.sort()\n",
    "        def dfs(x,ls):\n",
    "            if x==n:\n",
    "                return 1\n",
    "            tp=0\n",
    "            if nums[x]-k not in ls:\n",
    "                ls.append(nums[x])\n",
    "                tp+=dfs(x+1,ls)\n",
    "                ls.pop()\n",
    "            tp+=dfs(x+1,ls)\n",
    "            return tp   \n",
    "        ret=dfs(0,[])\n",
    "        return ret-1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def beautifulSubsets(self, nums: List[int], k: int) -> int:  #[2,3,5,7], 2\n",
    "        nums.sort()\n",
    "        res,flag = -1, [0] * (nums[-1] + 1)\n",
    "        def dfs(idx):\n",
    "            if idx >= len(nums):\n",
    "                nonlocal res\n",
    "                res += 1\n",
    "                return\n",
    "            x = nums[idx]\n",
    "            if x - k < 0 or flag[x-k] == 0:\n",
    "                flag[x] += 1\n",
    "                dfs(idx+1)\n",
    "                flag[x] -= 1\n",
    "            dfs(idx+1)\n",
    "        dfs(0)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def beautifulSubsets(self, nums: List[int], k: int) -> int:\n",
    "        nums.sort()\n",
    "        n = len(nums)\n",
    "        z = [0] * n\n",
    "        for i in range(n):\n",
    "            z[i] = 1<< i\n",
    "            for j in range(i+1, n):\n",
    "                if nums[j] - nums[i] ==k:\n",
    "                    z[i] |= 1<<j\n",
    "\n",
    "        @cache\n",
    "        def check(m):\n",
    "            for i in range(n):\n",
    "                if (m & (1<<i)) == 0:\n",
    "                    return check(m | ( 1<<i) )  + check( m| z[i])\n",
    "            return 1\n",
    "        \n",
    "        return check(0) - 1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def beautifulSubsets(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        nums.sort()\n",
    "        ans = 0\n",
    "        vis = [0] * 2001\n",
    "        def dfs(u):\n",
    "            nonlocal ans\n",
    "            if u == n:\n",
    "                ans += 1\n",
    "                return\n",
    "            dfs(u + 1)\n",
    "            if vis[nums[u] - k + 1000]:\n",
    "                return\n",
    "            vis[nums[u] + 1000] += 1\n",
    "            dfs(u + 1)\n",
    "            vis[nums[u] + 1000] -= 1\n",
    "        dfs(0)\n",
    "        return ans - 1\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def beautifulSubsets(self, nums: List[int], k: int) -> int:\n",
    "        ans = -1\n",
    "        n = len(nums)\n",
    "        check = [0] * 1005\n",
    "\n",
    "        def dfs(i: int) -> None:\n",
    "            if i == n:\n",
    "                nonlocal ans\n",
    "                ans += 1\n",
    "                return\n",
    "            # 不选\n",
    "            dfs(i + 1)\n",
    "            # 选\n",
    "            x = nums[i]\n",
    "            if not((1 <= x - k <= 1000 and check[x - k]) \\\n",
    "            or (1 <= x + k <= 1000 and check[x + k])):\n",
    "                check[x] += 1\n",
    "                dfs(i + 1)\n",
    "                check[x] -= 1\n",
    "        dfs(0)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def beautifulSubsets(self, nums: List[int], k: int) -> int:\n",
    "        n=len(nums)\n",
    "        ans=-1\n",
    "        mx=max(nums)\n",
    "        mi=min(nums)\n",
    "        cnt=[0]*(mx+k+1)\n",
    "\n",
    "        nums.sort()\n",
    "        \n",
    "        def dfs(i):\n",
    "            nonlocal ans\n",
    "            ans+=1\n",
    "            if i==n:\n",
    "                return \n",
    "            for j in range(i,n):\n",
    "                x=nums[j]\n",
    "                if x-k>=mi:\n",
    "                    if cnt[x-k] ==0 and cnt[x+k]==0:\n",
    "                        cnt[x]+=1\n",
    "                        dfs(j+1)\n",
    "                        cnt[x]-=1\n",
    "                if x-k<mi:\n",
    "                    if cnt[x+k]==0:\n",
    "                        cnt[x]+=1\n",
    "                        dfs(j+1)\n",
    "                        cnt[x]-=1\n",
    "            return \n",
    "        dfs(0)\n",
    "        return ans\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def beautifulSubsets(self, nums: List[int], k: int) -> int:\n",
    "        cnt = [0] * 2005\n",
    "        res = -1\n",
    "        def dfs(i):\n",
    "            if i == len(nums):\n",
    "                nonlocal res\n",
    "                res += 1\n",
    "                return\n",
    "            #不选\n",
    "            dfs(i + 1)\n",
    "\n",
    "            #如果可以选择nums[i]\n",
    "            x = nums[i]\n",
    "            if not cnt[x - k] and not cnt[x + k]:\n",
    "                cnt[x] += 1\n",
    "                dfs(i + 1)\n",
    "                cnt[x] -= 1\n",
    "        dfs(0)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def beautifulSubsets(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        nums.sort()\n",
    "        ans = 0\n",
    "        vis = [0] * 2001\n",
    "        def dfs(u):\n",
    "            nonlocal ans\n",
    "            if u == n:\n",
    "                ans += 1\n",
    "                return\n",
    "            dfs(u + 1)\n",
    "            if vis[nums[u] - k + 1000]:\n",
    "                return\n",
    "            vis[nums[u] + 1000] += 1\n",
    "            dfs(u + 1)\n",
    "            vis[nums[u] + 1000] -= 1\n",
    "        dfs(0)\n",
    "        return ans - 1\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def beautifulSubsets(self, nums: List[int], k: int) -> int:\n",
    "        nums.sort()\n",
    "        N = nums.__len__()\n",
    "        muted = [0]*(max(nums)+1)\n",
    "\n",
    "        def dfs(i):\n",
    "            if i == N:\n",
    "                return 0\n",
    "            res = 0\n",
    "            if muted[nums[i]] == 0:  # 当前可选\n",
    "                if nums[i]+k < muted.__len__():\n",
    "                    muted[nums[i]+k] += 1\n",
    "                res += dfs(i+1)+1\n",
    "                if nums[i]+k < muted.__len__():\n",
    "                    muted[nums[i]+k] -= 1\n",
    "            res += dfs(i+1)  # 不选\n",
    "            return res\n",
    "\n",
    "        return dfs(0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def beautifulSubsets(self, nums: List[int], k: int) -> int:\n",
    "        nums.sort()\n",
    "        N = nums.__len__()\n",
    "        cnts = [0]*(max(nums)+1)\n",
    "        for n in nums:\n",
    "            cnts[n] += 1\n",
    "\n",
    "        def dfs(beg):\n",
    "            if beg == N:\n",
    "                return 0\n",
    "            res = 0\n",
    "            if cnts[nums[beg]] > 0:  # 当前可选\n",
    "                flag = False\n",
    "                if nums[beg]+k < cnts.__len__() and cnts[nums[beg]+k] > 0:\n",
    "                    cnts[nums[beg]+k] = -cnts[nums[beg]+k]\n",
    "                    flag = True\n",
    "                res += dfs(beg+1)+1\n",
    "                if flag:\n",
    "                    cnts[nums[beg]+k] = -cnts[nums[beg]+k]\n",
    "            res += dfs(beg+1)  # 不选\n",
    "            return res\n",
    "\n",
    "        return dfs(0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def beautifulSubsets(self, nums: List[int], k: int) -> int:\n",
    "        ans = -1  # 去掉空集\n",
    "        # cnt = [0] * (max(nums) + k * 2)  # 用数组实现比哈希表更快\n",
    "        cnt = [0] * (max(nums) + k  + 1)\n",
    "        def dfs(i: int) -> None:\n",
    "            if i == len(nums):\n",
    "                nonlocal ans\n",
    "                ans += 1\n",
    "                return\n",
    "            dfs(i + 1)  # 不选\n",
    "            x = nums[i]\n",
    "            if cnt[x - k] == 0 and cnt[x + k] == 0:\n",
    "                cnt[x] += 1  # 选\n",
    "                dfs(i + 1)\n",
    "                cnt[x] -= 1  # 恢复现场\n",
    "        dfs(0)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def beautifulSubsets(self, nums: List[int], k: int) -> int:\n",
    "        length = len(nums)\n",
    "        used = [0] * (max(nums) + k + 1)\n",
    "        # path = []\n",
    "        # ans = []\n",
    "        self.count = 0\n",
    "        def dfs(start):\n",
    "\n",
    "            self.count += 1\n",
    "            for i in range(start, length):\n",
    "                val = nums[i]\n",
    "                if used[val + k] != 0 or used[val - k] != 0:\n",
    "                    continue\n",
    "\n",
    "                used[val] += 1\n",
    "                dfs(i + 1)\n",
    "                used[val] -= 1\n",
    "\n",
    "        dfs(0)\n",
    "        return self.count - 1\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def beautifulSubsets(self, nums: List[int], k: int) -> int:\n",
    "        n=len(nums)\n",
    "        ans=0\n",
    "        vis=[0 for i in range(max(nums)+k+1)]\n",
    "        def dfs(pos):\n",
    "            nonlocal ans\n",
    "            if pos==n:\n",
    "                ans+=1\n",
    "                return\n",
    "            dfs(pos+1)\n",
    "            if vis[nums[pos]-k]==0 and vis[nums[pos]+k]==0:\n",
    "                vis[nums[pos]]+=1\n",
    "                dfs(pos+1)\n",
    "                vis[nums[pos]]-=1\n",
    "                \n",
    "                   \n",
    "        dfs(0)\n",
    "        return ans-1\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def beautifulSubsets(self, nums: List[int], k: int) -> int:\n",
    "        n=len(nums)\n",
    "        ans=-1\n",
    "        mx=max(nums)\n",
    "        mi=min(nums)\n",
    "        cnt=[0]*(mx+k+1)\n",
    "\n",
    "        nums.sort()\n",
    "        \n",
    "        def dfs(i):\n",
    "            nonlocal ans\n",
    "            ans+=1\n",
    "            if i==n:\n",
    "                return \n",
    "            for j in range(i,n):\n",
    "                x=nums[j]\n",
    "                if x-k>=0:\n",
    "                    if cnt[x-k] ==0 and cnt[x+k]==0:\n",
    "                        cnt[x]+=1\n",
    "                        dfs(j+1)\n",
    "                        cnt[x]-=1\n",
    "                if x-k<0:\n",
    "                    if cnt[x+k]==0:\n",
    "                        cnt[x]+=1\n",
    "                        dfs(j+1)\n",
    "                        cnt[x]-=1\n",
    "            return \n",
    "        dfs(0)\n",
    "        return ans\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from math import *\n",
    "from queue import PriorityQueue,Queue\n",
    "from typing import *\n",
    "from heapq import *\n",
    "from functools import lru_cache,cache\n",
    "from string import *\n",
    "from itertools import product\n",
    "from collections import defaultdict\n",
    "\n",
    "# by hangpengjie\n",
    "class Solution:\n",
    "    def beautifulSubsets(self, nums: List[int], k: int) -> int:\n",
    "        nums.sort()\n",
    "        s = [0] * (1001)\n",
    "        n = len(nums)\n",
    "        def f(idx:int)->int:\n",
    "            if idx == n:\n",
    "                return 1\n",
    "            if nums[idx] - k >= 0 and s[nums[idx] - k]:\n",
    "                return f(idx + 1)\n",
    "            s[nums[idx]] += 1\n",
    "            r = f(idx + 1)\n",
    "            s[nums[idx]] -= 1\n",
    "            r += f(idx + 1)\n",
    "            return r\n",
    "        return f(0) - 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def beautifulSubsets(self, nums: List[int], k: int) -> int:\n",
    "\n",
    "        res = -1\n",
    "        n = len(nums)\n",
    "        \n",
    "\n",
    "        cnt = [0] * (max(nums) + k + 1)\n",
    "\n",
    "        def backtrack(index: int):\n",
    "            nonlocal res\n",
    "            res += 1\n",
    "            if index >= n:\n",
    "                return\n",
    "            for i in range(index, n):\n",
    "                if cnt[nums[i] - k] == 0 and cnt[nums[i] + k] == 0:\n",
    "                    cnt[nums[i]]+=1\n",
    "                    backtrack(i+1)\n",
    "                    cnt[nums[i]]-=1\n",
    "                    \n",
    "\n",
    "\n",
    "        backtrack(0)\n",
    "\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def beautifulSubsets(self, nums: List[int], k: int) -> int:\n",
    "        n=len(nums)\n",
    "        ans=0\n",
    "        vis=[0 for i in range(max(nums)+k+1)]\n",
    "        def dfs(pos):\n",
    "            nonlocal ans\n",
    "            if pos==n:\n",
    "                ans+=1\n",
    "                return\n",
    "            dfs(pos+1)\n",
    "            if vis[nums[pos]-k]==0 and vis[nums[pos]+k]==0:\n",
    "                vis[nums[pos]]+=1\n",
    "                dfs(pos+1)\n",
    "                vis[nums[pos]]-=1\n",
    "                \n",
    "        dfs(0)\n",
    "        return ans-1\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def beautifulSubsets(self, nums: List[int], k: int) -> int:\n",
    "        cnt=[0]*(max(nums)+k+1)\n",
    "        ans=-1\n",
    "        def dfs(i):\n",
    "            nonlocal ans\n",
    "            ans+=1\n",
    "            if i==len(nums):\n",
    "                return \n",
    "            for j in range(i, len(nums)):\n",
    "                x=nums[j]\n",
    "                if cnt[x-k]==0 and cnt[x+k]==0:\n",
    "                    cnt[x]+=1\n",
    "                    dfs(j+1)\n",
    "                    cnt[x]-=1\n",
    "        dfs(0)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def beautifulSubsets(self, nums: List[int], k: int) -> int:\n",
    "        vis = [0]*1000\n",
    "        def dfs(i):\n",
    "            res = 0\n",
    "            if i==len(nums):return 0\n",
    "            if (not 0<=nums[i]-k-1<1000 or not vis[nums[i]-k-1]) and (not 0<=nums[i]+k-1<1000 or not vis[nums[i]+k-1]):\n",
    "                vis[nums[i]-1]+=1\n",
    "                res+=1\n",
    "                res+=dfs(i+1)\n",
    "                vis[nums[i]-1]-=1\n",
    "            return res+dfs(i+1)\n",
    "        return dfs(0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def beautifulSubsets(self, nums: List[int], k: int) -> int:\n",
    "        nums.sort()\n",
    "        # @cache\n",
    "        def count(nums):\n",
    "            if not nums:\n",
    "                return 0\n",
    "            ans = 1\n",
    "            _nums = tuple(num for num in nums[1:] if num != nums[0] + k)\n",
    "            return 1 + count(_nums) + count(nums[1:])\n",
    "        \n",
    "        return count(tuple(nums))\n",
    "        \n",
    "        \n",
    "#         C = [0] * 2002\n",
    "#         total = 0\n",
    "#         n = len(nums)\n",
    "#         ans = 0\n",
    "#         print(nums)\n",
    "#         for i, v in enumerate(nums):\n",
    "#             tmp = total - C[v] + 1\n",
    "            \n",
    "#             for j in range(v + 1, 2002):\n",
    "#                 if C[j]:\n",
    "#                     C[j] *= 2\n",
    "#             print(total, v, C[v])\n",
    "#             ans += tmp\n",
    "#             total += tmp\n",
    "#             C[v + k] += tmp\n",
    "#             print(sum(C))\n",
    "#             print(C)\n",
    "#         return ans\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def beautifulSubsets(self, nums: List[int], k: int) -> int:\n",
    "\n",
    "        res = -1\n",
    "        n = len(nums)\n",
    "        \n",
    "\n",
    "        cnt = [0] * (max(nums) + k + 1)\n",
    "\n",
    "        def backtrack(index: int):\n",
    "            nonlocal res\n",
    "            res += 1\n",
    "            if index >= n:\n",
    "                return\n",
    "            for i in range(index, n):\n",
    "                if cnt[nums[i] - k] == 0 and cnt[nums[i] + k] == 0:\n",
    "                    cnt[nums[i]]+=1\n",
    "                    backtrack(i+1)\n",
    "                    cnt[nums[i]]-=1\n",
    "                    \n",
    "\n",
    "\n",
    "        backtrack(0)\n",
    "\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def beautifulSubsets(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        ans = -1\n",
    "        vis = [0] * (max(nums) + k*2)  # 用于判断是否已经选择过了，类似path\n",
    "        def dfs(idx):\n",
    "            if idx == n:\n",
    "                nonlocal ans\n",
    "                ans += 1\n",
    "                return\n",
    "            # 不选\n",
    "            dfs(idx+1)\n",
    "            x = nums[idx]\n",
    "            if vis[x - k] == 0 and vis[x + k] == 0:\n",
    "                # 选\n",
    "                vis[x] += 1\n",
    "                dfs(idx+1)\n",
    "                vis[x] -= 1\n",
    "            return\n",
    "        dfs(0)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def beautifulSubsets(self, nums: List[int], k: int) -> int:\n",
    "        ans=-1\n",
    "        cnt=[0]*(max(nums)+k*2)\n",
    "        def dfs(i):\n",
    "            if i==len(nums):\n",
    "                nonlocal ans\n",
    "                ans+=1\n",
    "                return\n",
    "            dfs(i+1)\n",
    "            x=nums[i]\n",
    "            if cnt[x-k]==0 and cnt[x+k]==0:\n",
    "                cnt[x]+=1\n",
    "                dfs(i+1)\n",
    "                cnt[x]-=1\n",
    "        dfs(0)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def beautifulSubsets(self, nums: List[int], k: int) -> int:\n",
    "        nums=sorted(nums)\n",
    "        result=[]\n",
    "        used=[0]*len(nums)\n",
    "        tmp=[0]*(max(nums)+k*2)\n",
    "        self.res=0\n",
    "        def dfs(l):\n",
    "            \n",
    "                # print(tmp)\n",
    "            self.res+=1\n",
    "            \n",
    "            for i in range(l,len(nums)):\n",
    "                n=nums[i]\n",
    "                # if used[i]: continue\n",
    "                if  tmp[n-k]  or  tmp[n+k]:\n",
    "                    continue\n",
    "                # used[i]+=1\n",
    "                tmp[n]+=1\n",
    "                dfs(i+1)\n",
    "                tmp[n]-=1\n",
    "                # used[i]=0\n",
    "        dfs(0)\n",
    "        # print(result)\n",
    "        return self.res-1\n",
    "\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def beautifulSubsets(self, nums: List[int], k: int) -> int:\n",
    "        ans = -1  # 去掉空集\n",
    "        cnt = [0] * (max(nums) + k * 2)  # 用数组实现比哈希表更快\n",
    "        def dfs(i: int) -> None:\n",
    "            if i == len(nums):\n",
    "                nonlocal ans\n",
    "                ans += 1\n",
    "                return\n",
    "            dfs(i + 1)  # 不选\n",
    "            x = nums[i]\n",
    "            if cnt[x - k] == 0 and cnt[x + k] == 0:\n",
    "                cnt[x] += 1  # 选\n",
    "                dfs(i + 1)\n",
    "                cnt[x] -= 1  # 恢复现场\n",
    "        dfs(0)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def beautifulSubsets(self, nums: List[int], k: int) -> int:\n",
    "        ans = -1  # 去掉空集\n",
    "        cnt = [0] * (max(nums) + k * 2)  # 用数组实现比哈希表更快\n",
    "        def dfs(i: int) -> None:  # 从 i 开始选\n",
    "            nonlocal ans\n",
    "            ans += 1\n",
    "            if i == len(nums):\n",
    "                return\n",
    "            for j in range(i, len(nums)):  # 枚举选哪个\n",
    "                x = nums[j]\n",
    "                if cnt[x - k] == 0 and cnt[x + k] == 0:\n",
    "                    cnt[x] += 1  # 选\n",
    "                    dfs(j + 1)\n",
    "                    cnt[x] -= 1  # 恢复现场\n",
    "        dfs(0)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def beautifulSubsets(self, nums: List[int], k: int) -> int:\n",
    "        # 1. 递归：选&不选\n",
    "        # ans = -1 # 去掉空寂\n",
    "        # cnt = [0] * (max(nums) + k * 2) # 用数组实现比哈希表更快\n",
    "        # def dfs(i:int) -> None:\n",
    "        #     if i == len(nums):\n",
    "        #         nonlocal ans\n",
    "        #         ans += 1\n",
    "        #         return\n",
    "        #     dfs(i + 1) # 不选\n",
    "        #     x = nums[i]\n",
    "        #     if cnt[x - k] == 0 and cnt[x + k] == 0:\n",
    "        #         cnt[x] += 1 # 选\n",
    "        #         dfs(i + 1) \n",
    "        #         cnt[x] -= 1 # 恢复现场\n",
    "        # dfs(0)\n",
    "        # return ans\n",
    "        # 2. 递归：枚举选哪个\n",
    "        ans = -1\n",
    "        cnt = [0] * (max(nums) + k * 2) # 用数组实现比哈希表更快\n",
    "        def dfs(i: int) -> None: # 从i开始\n",
    "            nonlocal ans\n",
    "            ans += 1\n",
    "            if i == len(nums):\n",
    "                return\n",
    "            for j in range(i, len(nums)): # 枚举选哪个\n",
    "                x = nums[j]\n",
    "                if cnt[x - k] == 0 and cnt[x + k] == 0:\n",
    "                    cnt[x] += 1\n",
    "                    dfs(j + 1)\n",
    "                    cnt[x] -= 1 # 恢复现场\n",
    "        dfs(0)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def beautifulSubsets(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        ans = -1\n",
    "        vis = [0] * (max(nums) + k*2)  # 用于判断是否已经选择过了，类似path\n",
    "        def dfs(start):\n",
    "            nonlocal ans\n",
    "            ans += 1\n",
    "            if start == n:\n",
    "                return\n",
    "            for idx in range(start, n):\n",
    "                x = nums[idx]\n",
    "                if vis[x-k] == 0 and vis[x+k] == 0:\n",
    "                    vis[x] += 1\n",
    "                    dfs(idx + 1)\n",
    "                    vis[x] -= 1\n",
    "            return\n",
    "        dfs(0)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def beautifulSubsets(self, nums: List[int], k: int) -> int:\n",
    "        n=len(nums)\n",
    "        ans=-1\n",
    "        cnt=[0]*(max(nums)+k*2)\n",
    "        def dfs(i):\n",
    "            if i==len(nums):\n",
    "                nonlocal ans\n",
    "                ans+=1\n",
    "                return\n",
    "            dfs(i+1)\n",
    "            x=nums[i]\n",
    "            if cnt[x-k]==0 and cnt[x+k]==0:\n",
    "                cnt[x]+=1\n",
    "                dfs(i+1)\n",
    "                cnt[x]-=1\n",
    "        dfs(0)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def beautifulSubsets(self, nums: List[int], k: int) -> int:\n",
    "        ans = -1  # 去掉空集\n",
    "        cnt = [0] * (max(nums) + k * 2)  # 用数组实现比哈希表更快\n",
    "        def dfs(i: int) -> None:\n",
    "            if i == len(nums):\n",
    "                nonlocal ans\n",
    "                ans += 1\n",
    "                return\n",
    "            dfs(i + 1)  # 不选\n",
    "            x = nums[i]\n",
    "            if cnt[x - k] == 0 and cnt[x + k] == 0:\n",
    "                cnt[x] += 1  # 选\n",
    "                dfs(i + 1)\n",
    "                cnt[x] -= 1  # 恢复现场\n",
    "        dfs(0)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def beautifulSubsets(self, nums: List[int], k: int) -> int:\n",
    "        # 美丽子集： 任意两个元素的差的绝对值不等于k\n",
    "        # 1. 递归：选&不选\n",
    "        # ans = -1 # 去掉空寂\n",
    "        # cnt = [0] * (max(nums) + k * 2) # 用数组实现比哈希表更快； 记录没有被选过的数\n",
    "        # def dfs(i:int) -> None:\n",
    "        #     if i == len(nums):\n",
    "        #         nonlocal ans\n",
    "        #         ans += 1\n",
    "        #         return\n",
    "        #     dfs(i + 1) # 不选\n",
    "        #     x = nums[i]\n",
    "        #     if cnt[x - k] == 0 and cnt[x + k] == 0:\n",
    "        #         cnt[x] += 1 # 选\n",
    "        #         dfs(i + 1) \n",
    "        #         cnt[x] -= 1 # 恢复现场\n",
    "        # dfs(0)\n",
    "        # return ans\n",
    "\n",
    "        # 2. 递归：枚举选哪个\n",
    "        ans = -1\n",
    "        cnt = [0] * (max(nums) + k * 2) # 用数组实现比哈希表更快\n",
    "        def dfs(i: int) -> None: # 从i开始\n",
    "            nonlocal ans\n",
    "            ans += 1\n",
    "            if i == len(nums):\n",
    "                return\n",
    "            for j in range(i, len(nums)): # 枚举选哪个\n",
    "                x = nums[j]\n",
    "                if cnt[x - k] == 0 and cnt[x + k] == 0: \n",
    "                    cnt[x] += 1\n",
    "                    dfs(j + 1)\n",
    "                    cnt[x] -= 1 # 恢复现场\n",
    "        dfs(0)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def beautifulSubsets(self, nums: List[int], k: int) -> int:\n",
    "        ans = -1  # 去掉空集\n",
    "        cnt = [0] * (max(nums) + k * 2)  # 用数组实现比哈希表更快\n",
    "        def dfs(i: int) -> None:  # 从 i 开始选\n",
    "            nonlocal ans\n",
    "            ans += 1\n",
    "            if i == len(nums):\n",
    "                return\n",
    "            for j in range(i, len(nums)):  # 枚举选哪个\n",
    "                x = nums[j]\n",
    "                if cnt[x - k] == 0 and cnt[x + k] == 0:\n",
    "                    cnt[x] += 1  # 选\n",
    "                    dfs(j + 1)\n",
    "                    cnt[x] -= 1  # 恢复现场\n",
    "        dfs(0)\n",
    "        return ans\n",
    "\n",
    " \n",
    "\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def beautifulSubsets(self, nums: List[int], k: int) -> int:\n",
    "        ans = -1  # 去掉空集\n",
    "        cnt = [0] * (max(nums) + k * 2)  # 用数组实现比哈希表更快\n",
    "        def dfs(i: int) -> None:\n",
    "            if i == len(nums):\n",
    "                nonlocal ans\n",
    "                ans += 1\n",
    "                return\n",
    "            dfs(i + 1)  # 不选\n",
    "            x = nums[i]\n",
    "            if cnt[x - k] == 0 and cnt[x + k] == 0:\n",
    "                cnt[x] += 1  # 选\n",
    "                dfs(i + 1)\n",
    "                cnt[x] -= 1  # 恢复现场\n",
    "        dfs(0)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def beautifulSubsets(self, nums: List[int], k: int) -> int:\n",
    "        nums.sort()\n",
    "        path = []\n",
    "        ans = 0\n",
    "        mp = [0] * 2009\n",
    "        def dfs(i: int):\n",
    "            if i < 0:\n",
    "                nonlocal ans\n",
    "                ans += 1\n",
    "                return\n",
    "            dfs(i - 1)\n",
    "            if mp[nums[i] + k] == 0:\n",
    "                path.append(nums[i])\n",
    "                mp[nums[i]] += 1\n",
    "                dfs(i - 1)\n",
    "                mp[nums[i]] -= 1\n",
    "                path.pop()\n",
    "        dfs(len(nums) - 1)\n",
    "        return ans - 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def beautifulSubsets(self, nums: List[int], k: int) -> int:\r\n",
    "        cnt = [0] * (max(nums) + k * 2)\r\n",
    "        ans = -1\r\n",
    "        def backtrack(start):\r\n",
    "            nonlocal ans\r\n",
    "            ans += 1\r\n",
    "            if start == len(nums):\r\n",
    "                return\r\n",
    "            for i in range(start, len(nums)):\r\n",
    "                cur = nums[i]\r\n",
    "                if cnt[cur - k] or cnt[cur + k]:\r\n",
    "                    continue\r\n",
    "                cnt[cur] += 1\r\n",
    "                backtrack(i + 1)\r\n",
    "                cnt[cur] -= 1\r\n",
    "        backtrack(0)\r\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def beautifulSubsets(self, nums: List[int], k: int) -> int:\n",
    "        # ans=[]\n",
    "        # n=len(nums)\n",
    "        # path=[]\n",
    "        # def dfs(i):\n",
    "        #     ans.append(path[:])\n",
    "        #     if i==n:\n",
    "\n",
    "        #         return\n",
    "        #     for j in range(i,n):\n",
    "        #         path.append(nums[j])\n",
    "        #         dfs(j+1)\n",
    "        #         path.pop()\n",
    "        # dfs(0)\n",
    "        # def isbeaut(lst,k):#判断是否有两个数之差绝对值等于k\n",
    "        #     m = len(lst)\n",
    "        #     flag = 0\n",
    "        #     for i in range(m):\n",
    "        #         for j in range(i, m):\n",
    "        #             if abs(lst[j] - lst[i]) == k:\n",
    "        #                 flag = 1\n",
    "        #                 break\n",
    "        #     if flag:\n",
    "        #         return False\n",
    "        #     else:\n",
    "        #         return True\n",
    "        # result=[]\n",
    "        # for a in ans:\n",
    "        #     if len(a)>0 and isbeaut(a,k):\n",
    "        #         result.append(a)\n",
    "        # return len(result)\n",
    "        ans = -1  # 去掉空集\n",
    "\n",
    "        cnt = [0] * (max(nums) + k * 2)  # 用数组实现比哈希表更快\n",
    "\n",
    "        def dfs(i: int) -> None:  # 从 i 开始选\n",
    "\n",
    "            nonlocal ans\n",
    "\n",
    "            ans += 1\n",
    "\n",
    "            if i == len(nums):\n",
    "\n",
    "                return\n",
    "\n",
    "            for j in range(i, len(nums)):  # 枚举选哪个\n",
    "\n",
    "                x = nums[j]\n",
    "\n",
    "                if cnt[x - k] == 0 and cnt[x + k] == 0:\n",
    "\n",
    "                    cnt[x] += 1  # 选\n",
    "\n",
    "                    dfs(j + 1)\n",
    "\n",
    "                    cnt[x] -= 1  # 恢复现场\n",
    "\n",
    "        dfs(0)\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def beautifulSubsets(self, nums: List[int], k: int) -> int:\n",
    "        ans = -1  # 去掉空集\n",
    "        cnt = [0] * (max(nums) + k * 2)  # 用数组实现比哈希表更快\n",
    "        def dfs(i: int) -> None:\n",
    "            if i == len(nums):\n",
    "                nonlocal ans\n",
    "                ans += 1\n",
    "                return\n",
    "            dfs(i + 1)  # 不选\n",
    "            x = nums[i]\n",
    "            if cnt[x - k] == 0 and cnt[x + k] == 0:\n",
    "                cnt[x] += 1  # 选\n",
    "                dfs(i + 1)\n",
    "                cnt[x] -= 1  # 恢复现场\n",
    "        dfs(0)\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def beautifulSubsets(self, s: List[int], k: int) -> int:\n",
    "        res = -1 # 去掉空集\n",
    "        cnt = [0] * (max(s) + k * 2)\n",
    "\n",
    "        \n",
    "        def dfs(start):\n",
    "            nonlocal res\n",
    "            res += 1\n",
    "            if start >= len(s):\n",
    "                return\n",
    "            \n",
    "            for i in range(start, len(s)):\n",
    "                x = s[i]\n",
    "                if cnt[x - k] == 0 and cnt[x + k] == 0:\n",
    "                    cnt[x] += 1\n",
    "                    dfs(i + 1)\n",
    "                    cnt[x] -= 1\n",
    "\n",
    "        dfs(0)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # # 回溯\n",
    "    # 子集型回溯\n",
    "    # 写法一：选或不选\n",
    "    # https://leetcode.cn/problems/the-number-of-beautiful-subsets/solution/tao-lu-zi-ji-xing-hui-su-pythonjavacgo-b-fcgs/\n",
    "    def beautifulSubsets1(self, nums: List[int], k: int) -> int:\n",
    "        ans = -1  # 去掉空集\n",
    "        cnt = [0] * (max(nums) + k * 2)  # 用数组实现比哈希表更快\n",
    "        def dfs(i: int) -> None:\n",
    "            if i == len(nums):\n",
    "                nonlocal ans\n",
    "                ans += 1\n",
    "                return\n",
    "\n",
    "            dfs(i + 1)  # 不选\n",
    "            x = nums[i]\n",
    "            if cnt[x - k] == 0 and cnt[x + k] == 0:\n",
    "                cnt[x] += 1  # 选\n",
    "                dfs(i + 1)\n",
    "                cnt[x] -= 1  # 恢复现场\n",
    "\n",
    "        dfs(0)\n",
    "        return ans\n",
    "\n",
    "\n",
    "\n",
    "    def beautifulSubsets(self, nums: List[int], k: int) -> int:\n",
    "        ans = -1  # 去掉空集\n",
    "        cnt = [0] * (max(nums) + k * 2)  # 用数组实现比哈希表更快\n",
    "        def dfs(i: int) -> None:  # 从 i 开始选\n",
    "            nonlocal ans\n",
    "            ans += 1\n",
    "            if i == len(nums):\n",
    "                return\n",
    "            for j in range(i, len(nums)):  # 枚举选哪个\n",
    "                x = nums[j]\n",
    "                if cnt[x - k] == 0 and cnt[x + k] == 0:\n",
    "                    cnt[x] += 1  # 选\n",
    "                    dfs(j + 1)\n",
    "                    cnt[x] -= 1  # 恢复现场\n",
    "\n",
    "        dfs(0)\n",
    "        return ans\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def beautifulSubsets(self, nums: List[int], k: int) -> int:\n",
    "        cnt=[0]*3000\n",
    "        n=len(nums)\n",
    "        ans=0\n",
    "        def dfs(i:int):\n",
    "            nonlocal ans\n",
    "            if i==len(nums)-1:\n",
    "                return\n",
    "            for j in range(i+1,len(nums)):\n",
    "                x=nums[j]\n",
    "                if cnt[x-k]==0 and cnt[x+k]==0:\n",
    "                    cnt[x]+=1\n",
    "                    ans+=1\n",
    "                    dfs(j)\n",
    "                    cnt[x]-=1\n",
    "        for i in range(len(nums)):\n",
    "            cnt[nums[i]]+=1\n",
    "            ans+=1\n",
    "            dfs(i)\n",
    "            cnt[nums[i]]-=1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def beautifulSubsets(self, nums: List[int], k: int) -> int:\n",
    "        N = len(nums)\n",
    "        ans = -1\n",
    "        x2cnt = [0 for _ in range(3001)]\n",
    "        def dfs(i):\n",
    "            if i < 0:\n",
    "                nonlocal ans\n",
    "                ans += 1\n",
    "                return\n",
    "\n",
    "            dfs(i-1)\n",
    "\n",
    "            if x2cnt[nums[i] - k] == 0 and x2cnt[nums[i] + k] == 0:\n",
    "                x2cnt[nums[i]] += 1\n",
    "                dfs(i-1)\n",
    "                x2cnt[nums[i]] -= 1\n",
    "        dfs(N-1)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def beautifulSubsets(self, nums: List[int], k: int) -> int:\n",
    "\n",
    "\n",
    "        n=len(nums)\n",
    "\n",
    "        ttl=[0]*(max(nums)+2*k+1)\n",
    "        def dfs(i):\n",
    "            if i<0:return 1\n",
    "            tans=0\n",
    "            if ttl[nums[i]-k]==0 and ttl[nums[i]+k]==0:\n",
    "                ttl[nums[i]]+=1\n",
    "                tans+=dfs(i-1) \n",
    "                ttl[nums[i]]-=1\n",
    "\n",
    "            tans+=dfs(i-1)\n",
    "            return tans\n",
    "        return dfs(n-1)-1  ##去除空集合"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
